Interconnect analysis for modern ICs has traditionally required large scale capacitance calculations. However, such analysis required the geometry of the ICs to be described in detail, which resulted in millions, or even billions, of polygonal elements. The interconnect analysis yielded a sparse capacitance matrix of dominant coupling coefficients between conductors (commonly called “nets”). A net is formed of metallic pieces that are located within the IC and coupled together such that they cooperate to conduct current between two points. The net also has a capacitance associated with it.
Traditionally, capacitance calculations have not required great accuracy (accuracies of 10-20% were acceptable). To achieve this relatively low accuracy, pattern matching schemes consisting of precharacterized libraries were used. However, nets such as clock nets, power grids, sensitive analog nodes or critical paths of a circuit require a higher accuracy in their solution. Unfortunately, as the requirement for accuracy increased, pattern matching solutions became insufficient.
Numerical approaches were then explored in an effort to increase the accuracy in capacitive calculations. Conventional numerical approaches rendered conductor surfaces (nets) in terms of discrete elements. Enforcing the equation either as a set of collocation points or as a distribution, as with a Galerkin scheme, led to a dense linear system. The large size of these systems usually required that they be solved with Krylov iterative methods. The required matrix-vector products were accelerated with compressed-matrix schemes (such as FastCap), pre-corrected Fast Fourier Transforms, or Singular Value Decomposition (“SVD”)-based representations. While these methods are capable of high accuracy, they are restricted to systems of only a few hundred thousand unknowns. Even with only one unknown per polygon, large problems having millions of polygons remained well beyond the reach of these methods.
The industry further tried what is conventionally termed a “random walk” method, based on the well-known Monte Carlo method. Unfortunately, the random walk method required a significant amount of central processing unit (“CPU”) time to achieve high accuracy. For this reason, larger problems involving millions of polygons, proved to be unsatisfactory.
Next, finite-difference or finite-element methods were attempted. These methods required that a three-dimensional mesh be imposed on the geometry of the capacitive structure. However, these methods created more unknowns than did other numerical methods, and therefore were even less desirable.
Accordingly, what is needed in the art is way to increase the accuracy of IC capacitance calculations without incurring excessive computational time or difficulty.